package cn.cxq.learning.stack;

import com.sun.corba.se.spi.orb.Operation;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器
 */
public class ReversePolish {

    /**
     * 中缀表达式转后缀表达式：
     * 1.碰到数字直接入中间结果
     * 2.碰到“（”直接入栈
     * 3.碰到“）”将所有的符号出栈直到碰到“（”
     * 4.其他普通符号判断优先级，如果优先级大于栈顶符号直接入栈，如果小于或等于栈顶富豪的优先级直接先出栈然后再压栈
     * 5.重复上述步骤直到字符串最末尾的一个字符
     * 6.将符号栈中剩下的符号加入到中间结果中产生最终结果。
     * @param infix
     * @return
     */
    public static String infixToPostfix(String infix){

        StringBuffer reversePolish = new StringBuffer(); //中间结果
        Stack<String> symbolStack = new Stack<>(); //符号栈

        List<String> list = convertTOArray(infix);

        for (String item : list) {
            //正则表达式判断是否为数字
            if (item.matches("\\d+\\.\\d+") ||item.matches("\\d+")){

                //插入中间值中，每个项用" "分隔
                reversePolish.append(item + " ");
            } else if (item.equals("(")){
                symbolStack.push(item);
            } else if (item.equals(")")){
                while (!symbolStack.peek().equals("(")){
                    reversePolish.append(symbolStack.pop() + " ");
                }
                symbolStack.pop();
            } else {
                while (!symbolStack.empty() && getPriority(symbolStack.peek())>=getPriority(item)){
                    reversePolish.append(symbolStack.pop() + " ");
                }
                symbolStack.push(item);
            }
        }

        //将剩余的符号出栈
        while (!symbolStack.empty()){
            if (symbolStack.size()!=1) reversePolish.append(symbolStack.pop() + " ");
            reversePolish.append(symbolStack.pop());
        }

        return reversePolish.toString();
    }

    private static List<String> convertTOArray(String infix) {
        ArrayList<String> list = new ArrayList<>();
        int index = 0;
        while (index < infix.length()){
            //符号直接进数组
            if (infix.charAt(index) < 48 || infix.charAt(index) >57) {
                list.add(String.valueOf(infix.charAt(index)));
                index ++;
            }
            //数字考虑多位
            else {
                StringBuffer buffer = new StringBuffer();
                while (index < infix.length() && (infix.charAt(index) >= 48 && infix.charAt(index) <= 57 || infix.charAt(index) == '.')) {
                    buffer.append(infix.charAt(index));
                    index ++;
                }
                list.add(buffer.toString());
            }
        }
        return list;
    }

    //返回符号的优先级
    private static int getPriority(String symbol){
        switch (symbol){
            case "(":
            case ")":
                return 0;
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            default:
                throw new RuntimeException("符号有误~~~");
        }
    }

    /**
     * 1.如果是数字的话就直接压栈
     * 2.碰上符号直接出栈两个数计算，把结果压栈
     * 3.重复1、2步直到字符串尾部
     * 4.把最后剩余的数出栈即是结果
     * @param postfix
     * @return
     */
    public static double calculate(String postfix){

        Stack<Double> numStack = new Stack<>();
        String[] split = postfix.split(" ");

        for (String item : split) {
            if (item.matches("\\d+\\.\\d+") ||item.matches("\\d+")) numStack.push(Double.parseDouble(item));
            else {
                double b = numStack.pop();
                double a = numStack.pop();
                double result = cal(a,b,item);
                numStack.push(result);
            }
        }

        return numStack.pop();
    }

    private static double cal(double a, double b, String symbol) {
        switch (symbol){
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            default:
                throw new RuntimeException("符号不合法~~~");
        }
    }
}
